/*
    从每个点都往外扩, 然后扩k次
*/

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 500;
vector<pii> head[N];
int n, m, k;
int d[N], t[N];
int bellman_ford(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 1; i <= k; i++){
        memcpy(t, d, sizeof t);
        for (int j = 1; j <= n; j++){
            if (d[j] < 0x3f3f3f3f){
                for (auto c : head[j]){
                    int x = c.first;
                    int dis = c.second;
                    if (d[j] + dis < t[x]){
                        t[x] = d[j] + dis;
                    }
                }
            }
        }
        memcpy(d, t, sizeof d);
    }
    if (d[n] < 0x3f3f3f3f) return d[n];
    return -1;
}

int main(){
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        head[a].push_back({b,c});
    }
    cout << bellman_ford();
    return 0;
}

